#include "util.h"
#include "cache.h"
struct reccache *rcnew(int nbucket,int maxpage,int pagesiz){
    struct reccache *rc=calloc(1,sizeof(struct reccache));
	rc->nbucket=nbucket;
	rc->maxpage=maxpage;
	rc->pagesiz=pagesiz;
	rc->buckets=calloc(rc->nbucket,sizeof(struct hashnode*));
	return rc;
}
void rcfree(struct reccache* rc){
    struct hashnode *hn=rc->first;
	if(hn!=NULL) hn->pre->next=NULL;
	while(hn!=NULL){
	    struct hashnode *t=hn;
		hn=hn->next;
		free(t);
		printf("%s:free use nodes\n",__func__);
	}
	hn=rc->freenodes;
	while(hn!=NULL){
	    struct hashnode *t=hn->next;
		free(hn);
		printf("%s:free free nodes\n",__func__);
		hn=t;
	}
	struct recpage *rp=rc->freelist;
	while(rp!=NULL){
	    struct recpage *t=rp->listnext;
		free(rp);
		printf("%s:free free page\n",__func__);
		rp=t;
	}
	rp=rc->fulllist;
	while(rp!=NULL){
	    struct recpage* t=rp->listnext;
		printf("%s:free full page rp=%d\n",__func__,rp);
		free(rp);
		rp=t;
	}
	rp=rc->halflist;
	if(rp!=NULL) rp->listpre->listnext=NULL;
	while(rp!=NULL){
	    struct recpage *t=rp->listnext;
		printf("%s:free halflist\n",__func__);
		free(rp);
		rp=t;
	}
	free(rc->buckets);
	free(rc);
}
struct recpage* recgetroom(struct reccache *rc,int siz){
	struct recpage *tt=rc->halflist;
	if(tt!=	NULL){
		printf("%s:rem siz=%d\n",__func__,tt->upper-tt->lower);
		tt=tt->listnext;
		while(tt!=rc->halflist){
			printf("%s:rem siz=%d\n",__func__,tt->upper-tt->lower);
			tt=tt->listnext;
		}
	}
    struct recpage *rp=rc->halflist;
	if(rp)	printf("%s:rp->upper-rp->lower=%d siz=%d\n",__func__,rp->upper-rp->lower,siz);
	if(rp!=NULL&&rp->upper-rp->lower>=siz){
	    if(rp->listnext!=rp){
		    rp->listnext->listpre=rp->listpre;
		    rp->listpre->listnext=rp->listnext;
			rc->halflist=rp->next;
		}else rc->halflist=NULL;
		return rp;
	}
	if(rp!=NULL){
		printf("%s:biggest room siz=%d\n",__func__,rp->listpre->upper-rp->listpre->lower);
	    if(rp->listpre->upper-rp->listpre->lower>=siz){
	        rp=rp->listnext;
	        while(rp!=rc->halflist&&rp->upper-rp->lower<siz){
		        printf("%s:page rem room=%d\n",__func__,rp->upper-rp->lower);
	            rp=rp->listnext;
	        }
		}else rp=NULL;
	}
	if(rp==NULL){
		printf("%s:create a new page\n",__func__);
	    rp=recnewpage(rc);
		rp->upper=rc->pagesiz;
		rp->lower=sizeof(struct recpage);
		rp->type=PAGE_FREE;
	}else{
		rp->listpre->listnext=rp->listnext;
		rp->listnext->listpre=rp->listpre;
	}
	return rp;
}
int halflistadd(struct reccache *rc,struct recpage* rp){
    struct recpage *t;
	int siz=rp->upper-rp->lower;
	rp->type=PAGE_HALF;
	printf("%s:siz=%d\n",__func__,rp->upper-rp->lower);
	if(rc->halflist==NULL){
	    rc->halflist=rp;
		rp->listpre=rp->listnext=rp;
		return 1;
	}
	t=rc->halflist->listpre;
	if(t->upper-t->lower<siz){
	    rp->listnext=t->listnext;
		rp->listpre=t;
		t->listnext->listpre=rp;
		t->listnext=rp;
		return 1;
	}else{
	    t=t->listpre;
	    while(t!=rc->halflist->listpre&&t->upper-t->lower>siz)
	        t=t->listpre;
	}
	if(t==rc->halflist->listpre) rc->halflist=rp;
	rp->listpre=t;
	rp->listnext=t->listnext;
	t->listnext->listpre=rp;
	t->listnext=rp;
	return 1;
}
int halflistremove(struct reccache *rc,struct recpage *rp){
    if(rp->listnext==rp){
	    rc->halflist=NULL;
		return 1;
	}
	if(rc->halflist==rp) rc->halflist=rp->listnext;
	rp->listpre->listnext=rp->listnext;
	rp->listnext->listpre=rp->listpre;
	return 1;
}
int rcput(struct reccache *rc,char *key,int ksiz,char *val,int vsiz){
    int siz=sizeof(struct recitem)+ksiz+vsiz;
	struct recpage *rp;
	struct recitem *ri;
	struct hashnode *hn;
	int id=rc->nextid++;
	int16 off;
	rc->nrec++;
	printf("%s:recordsiz=%d rc->pagesiz=%d sizeof(struct recpage)=%d\n",__func__,siz,rc->pagesiz,sizeof(struct recpage));
	if(siz<=rc->pagesiz-sizeof(struct recpage)-sizeof(struct recitem)
	   &&(rp=recgetroom(rc,siz+sizeof(int16)))!=NULL){
	    if((hn=hashnodeput(rc,rp,id,key,ksiz,vsiz))==NULL){
		    if(rp->type==PAGE_FREE) freelistadd(rc,rp);
			else halflistadd(rc,rp);
			printf("%s:put to cache fail\n",__func__);
			return 0;
		}
		rp->upper-=siz;
	    ri=(struct recitem*)((char*)rp+rp->upper);
	    ri->id=id;
		ri->siz=siz;
		memcpy((char*)(ri+1),key,ksiz);
		memcpy((char*)(ri+1)+ksiz,val,vsiz);
		*((int16*)((char*)rp+rp->lower))=rp->upper;
		rp->lower+=sizeof(int16);
		if(rp->type==PAGE_FREE){
			if(rp->upper-rp->lower<RECCACHE_RECMINSIZ){
			    fulllistadd(rc,rp);
			}else halflistadd(rc,rp);
		}else if(rp->type==PAGE_HALF){
		    if(rp->upper-rp->lower<RECCACHE_RECMINSIZ)
			    fulllistadd(rc,rp);
			else
			    halflistadd(rc,rp);
		}
		return 1;
	}
	rp=recnewpage(rc);
	if((hn=hashnodeput(rc,rp,id,key,ksiz,vsiz))==NULL){
	    freelistadd(rc,rp);
		return 0;
	}
	hn->flag=HN_PIN;
	char buf[RECCACHE_BUFSIZ];
	char *tb=buf,*ptr,*target;
	int cpsiz;
	if(ksiz+vsiz>RECCACHE_BUFSIZ){
	    tb=malloc(ksiz+vsiz);
	}
	ptr=tb;
	cpsiz=rc->pagesiz-sizeof(struct recpage)-sizeof(int16)-sizeof(struct recitem);
	ri=(struct recitem*)((char*)rp+sizeof(struct recpage)+sizeof(int16));
	ri->id=id;
	ri->siz=siz;
	target=(char*)ri+sizeof(struct recitem);
	memcpy(tb,key,ksiz);
	memcpy(tb+ksiz,val,vsiz);
	memcpy(target,ptr,cpsiz);
	siz-=cpsiz;
	rp->upper=sizeof(struct recpage)+sizeof(int16);
	printf("%s:upper=%d\n",__func__,rp->upper);
	*((int16*)((char*)rp+sizeof(struct recpage)))=rp->upper;
	rp->lower=sizeof(struct recpage)+sizeof(int16);
	fulllistadd(rc,rp);
	ptr+=cpsiz;
	cpsiz=rc->pagesiz-sizeof(struct recpage);
	while(siz>0){
	    rp->next=recnewpage(rc);
		rp=rp->next;
	    if(siz<cpsiz){
		    rp->upper=rc->pagesiz-siz;
			printf("%s:rem page upper=%d\n",__func__,rp->upper);
		    memcpy((char*)rp+rp->upper,ptr,siz);
			rp->lower=sizeof(struct recpage);
			rp->next=NULL;
			if(rp->upper-rp->lower>=RECCACHE_RECMINSIZ){
			    halflistadd(rc,rp);
			}else fulllistadd(rc,rp);
			break;
		}else{
		    memcpy(rp+1,ptr,cpsiz);
			rp->upper=rc->pagesiz-cpsiz;
			rp->lower=sizeof(struct recpage);
			fulllistadd(rc,rp);
			siz-=cpsiz;
			ptr+=cpsiz;
		}
	}
	hn->flag&=~HN_PIN;
	if(tb!=buf) free(tb);
	return 1;
}
int _hashnoderemove(struct reccache *rc,struct hashnode *hn,int pos){
    uint32 hash1=hn->hash1%rc->nbucket;
	struct hashnode *t=rc->buckets[hash1];
	struct hashnode *pt=t;
	int cmp;
	uint16 hash2=hn->hash1&0x0000FFFF;
	uint16 hv2;
	struct recitem *r1,*r2;
	r1=(struct recitem*)((char*)hn->rp+*(((int16*)(char*)hn->rp+sizeof(struct recpage))+pos));
	while(t!=NULL){
	    hv2=t->hash1&0x0000FFFF;
	    if(hv2>hash2){
		    pt=t;
			t=t->left;
		}else if(hv2<hash2){
		    pt=t;
			t=t->right;
		}else if(hn->id!=t->id){//some problem
			r2=recsearch(rc,t->rp,t->id,NULL);
			int cmpsiz=hn->ksiz>t->ksiz?t->ksiz:hn->ksiz;
			cmp=reccmp(rc,t->rp,r2,hn->rp,r1,cmpsiz);
			if(cmp==0) cmp=t->ksiz-hn->ksiz;
		    if(cmp>0){
			    pt=t;
				t=t->left;
			}else if(cmp<0){
			    pt=t;
				t=t->right;
			}else{
			    printf("%s:bad same key find\n",__func__);
				exit(1);
			}
		}else break;
	}
	if(t==NULL){
	    printf("locate error\n");
		exit(1);
	}
	if(t->left==NULL){
	    if(pt==t) rc->buckets[hash1]=t->right; 
	    else if(pt->left==t) pt->left=t->right;
		else pt->right=t->right;
	}
	else if(t->right==NULL){
	    if(pt==t) rc->buckets[hash1]=t->left;
	    else if(pt->left==t) pt->left=t->left;
	    else pt->right=t->left;
	}
	else{
	    struct hashnode *lnp=t->left;
		struct hashnode *ln=lnp;
		while(ln->right!=NULL){
		    lnp=ln;
			ln=ln->right;
		}
		if(pt==t) rc->buckets[hash1]=ln;
		else if(pt->left==t) pt->left=ln;
		else pt->right=ln;
		if(ln!=lnp){
		    lnp->right=ln->left;
		    ln->left=t->left;
		}
		ln->right=t->right;
	}
	if(hn->pre==hn) rc->first=NULL;
	else{
	    hn->pre->next=hn->next;
		hn->next->pre=hn->pre;
		if(hn==rc->first) rc->first=hn->next;
	}
	return 1;
}
int rcremove(struct reccache *rc,char *key,int ksiz){
	uint32 hash1=hash_fun(key,ksiz);
	uint16 hash2=hash1&0x0000FFFF;
	int cmp,pos;
	struct recitem *ri;
	hash1%=rc->nbucket;
	struct hashnode *hn=rc->buckets[hash1];
	while(hn!=NULL){
	    uint32 hv2=hn->hash1&0x0000FFFF;
	    if(hv2>hash2){
		    hn=hn->left;
		}else if(hv2<hash2){
		    hn=hn->right;
		}else{
		    ri=recsearch(rc,hn->rp,hn->id,&pos);
			int cmpsiz=hn->ksiz>ksiz?ksiz:hn->ksiz;
		    cmp=reccmpstr(rc,hn->rp,ri,key,cmpsiz);
			if(cmp==0) cmp=hn->ksiz-ksiz;
			printf("%s:search ok.id=%d,cmpsiz=%d cmp=%d\n",__func__,hn->id,cmpsiz,cmp);
			if(cmp<0){
			    hn=hn->left;
			}else if(cmp>0){
			    hn=hn->right;
			}else{
			    break;
			}
		}
	}
	if(hn==NULL) return 0;
	_hashnoderemove(rc,hn,pos);
	//printf("%s:id=%d pos=%d\n",__func__,hn->id,pos);
	recfree(rc,hn->rp,pos);
	//	printf("%s:free %d pg\n",__func__,npg);
	hashnodefree(rc,hn);
	return 1;
}
char* rcget(struct reccache *rc,char *key,int ksiz,char *buf,int *siz){
    uint32 hash1=hash_fun(key,ksiz);
	uint16 hash2=hash1&0x0000FFFF;
	int cmp;
	struct recitem *ri;
	hash1%=rc->nbucket;
	struct hashnode *hn=rc->buckets[hash1];
	while(hn!=NULL){
	    uint32 hv2=hn->hash1&0x0000FFFF;
	    if(hv2>hash2){
		    hn=hn->left;
		}else if(hv2<hash2){
		    hn=hn->right;
		}else{
		    ri=recsearch(rc,hn->rp,hn->id,NULL);
			int cmpsiz=hn->ksiz>ksiz?ksiz:hn->ksiz;
		    cmp=reccmpstr(rc,hn->rp,ri,key,cmpsiz);
			if(cmp==0) cmp=hn->ksiz-ksiz;
			printf("%s:search ok.id=%d,cmpsiz=%d cmp=%d\n",__func__,hn->id,cmpsiz,cmp);
			if(cmp<0){
			    hn=hn->left;
			}else if(cmp>0){
			    hn=hn->right;
			}else{
			    break;
			}
		}
	}
	if(hn==NULL) return NULL;
	if(hn->vsiz>*siz) buf=malloc(hn->vsiz);
	*siz=hn->vsiz;
	reccpy(rc,hn->rp,ri,ksiz+sizeof(struct recitem),buf,hn->vsiz);
	if(hn!=rc->first){
	    hn->pre->next=hn->next;
		hn->next->pre=hn->pre;
	    hn->pre=rc->first->pre;
		hn->next=rc->first;
		rc->first->pre->next=hn;
		rc->first->next->pre=hn;
		rc->first=hn;
	}
	return buf;
}
struct hashnode *getrecnode(struct reccache *rc,char *key,int ksiz,int *pos){
	uint32 hash1=hash_fun(key,ksiz);
	uint16 hash2=hash1&0x0000FFFF;
	int cmp;
	struct recitem *ri;
	hash1%=rc->nbucket;
	struct hashnode *hn=rc->buckets[hash1];
	while(hn!=NULL){
	    uint32 hv2=hn->hash1&0x0000FFFF;
	    if(hv2>hash2){
		    hn=hn->left;
		}else if(hv2<hash2){
		    hn=hn->right;
		}else{
		    ri=recsearch(rc,hn->rp,hn->id,pos);
			int cmpsiz=hn->ksiz>ksiz?ksiz:hn->ksiz;
		    cmp=reccmpstr(rc,hn->rp,ri,key,cmpsiz);
			if(cmp==0) cmp=hn->ksiz-ksiz;
			printf("%s:search ok.id=%d,cmpsiz=%d cmp=%d\n",__func__,hn->id,cmpsiz,cmp);
			if(cmp<0){
			    hn=hn->left;
			}else if(cmp>0){
			    hn=hn->right;
			}else{
			    break;
			}
		}
	}
	return hn;
}
int rcgetval(struct reccache *rc,struct hashnode *hn,int pos,char *buf,int siz){
	int cpsiz=hn->vsiz>siz?siz:hn->vsiz;
	char *ptr=(char*)hn->rp+sizeof(struct recpage)+sizeof(int16)*pos;
	struct recitem *ri=(struct recitem*)((char*)hn->rp+*((int16*)ptr));
	reccpy(rc,hn->rp,ri,hn->ksiz+sizeof(struct recitem),buf,cpsiz);
	if(hn!=rc->first){
	    hn->pre->next=hn->next;
		hn->next->pre=hn->pre;
	    hn->pre=rc->first->pre;
		hn->next=rc->first;
		rc->first->pre->next=hn;
		rc->first->next->pre=hn;
		rc->first=hn;
	}
	return cpsiz;
}
int reccpy(struct reccache *rc,struct recpage* rp,struct recitem *ri,int off,char *buf,int bsiz){
    if(off>ri->siz) return 0;
	int cpsiz=ri->siz-off>bsiz?bsiz:ri->siz-off;
	int siz=rc->pagesiz-sizeof(struct recpage)-sizeof(int16);
	char *ptr=buf;
	int len,upper;
	int head=1;
	if(ri->siz+sizeof(int16)>siz){
	    printf("%s:id=%d recsiz=%d cpsiz=%d off=%d\n",__func__,ri->id,ri->siz,cpsiz,off);
	    while(off>siz&&rp!=NULL){
		    off-=siz;
			rp=rp->next;
			siz=rc->pagesiz-sizeof(struct recpage);
			head=0;
		}
		if(rp==NULL){
		    printf("%s:error",__func__);
			exit(1);
		}
		if(!head&&rp->lower>sizeof(struct recpage)){
		    upper=*((int16*)((char*)rp+sizeof(struct recpage)));
			struct recitem *ri=(struct recitem*)((char*)rp+upper);
			upper+=ri->siz;
		}
		else upper=rp->upper;
		len=rc->pagesiz-upper-off>cpsiz?cpsiz:rc->pagesiz-upper-off;
		printf("%s:upper=%d len=%d rp->upper=%d\n",__func__,upper,len,rp->upper);
		memcpy(ptr,off+upper+(char*)rp,len);
		ptr+=len;
		rp=rp->next;
		while(rp!=NULL&&len<cpsiz){
		    if(rp->lower>sizeof(struct recpage)){
		        upper=*((int16*)((char*)rp+sizeof(struct recpage)));
			    struct recitem *ri=(struct recitem*)((char*)rp+upper);
			    upper+=ri->siz;
		    }
			else upper=rp->upper;
			int cplen=cpsiz-len>rc->pagesiz-upper?rc->pagesiz-upper:cpsiz-len;
			printf("%s:upper=%d cplen=%d\n",__func__,upper,cplen);
			memcpy(ptr,upper+(char*)rp,cplen);
			len+=cplen;
			ptr+=cplen;
		}
	}else{
	    memcpy(buf,(char*)ri+off,cpsiz);
	}
	return cpsiz;
}
struct recpage *recnewpage(struct reccache *rc){
    struct recpage *p;
	if(rc->freelist!=NULL){
	    p=rc->freelist;
		rc->freelist=p->listnext;
		return p;
	}
	if(rc->npage<rc->maxpage){
	    rc->npage++;
		printf("%s:create a new page:npg=%d\n",__func__,rc->npage);
	    return malloc(rc->pagesiz);
	}
	hashswap(rc);
	if(rc->freelist==NULL){
	    rc->npage++;
	    return malloc(rc->pagesiz);
	}
	p=rc->freelist;
	rc->freelist=p->listnext;
	return p;
}
struct hashnode *hashnodealloc(struct reccache *rc){
    if(rc->freenodes==NULL){
	    return malloc(sizeof(struct hashnode));
	}
	struct hashnode *hn=rc->freenodes;
	rc->freenodes=hn->next;
	return hn;
}
void hashnodefree(struct reccache *rc,struct hashnode *hn){
    hn->next=rc->freenodes;
	rc->freenodes=hn;
}
struct hashnode* hashnodeput(struct reccache *rc,struct recpage *rp,int id,char *key,int ksiz,int vsiz){
    uint32 hash1=hash_fun(key,ksiz);
	struct hashnode *hn=hashnodealloc(rc);
	int cmp;
	struct hashnode *n,*pn;
	hn->hash1=hash1;
	hash1=hash1%rc->nbucket;
	uint16 hash2=hn->hash1&0x0000FFFF,hv2;
	hn->rp=rp;
	hn->id=id;
	hn->ksiz=ksiz;
	hn->vsiz=vsiz;
	hn->left=hn->right=NULL;
	printf("%s:ohash1=%d hash1=%d\n",__func__,hn->hash1,hash1);
	if(rc->buckets[hash1]==NULL){
	    rc->buckets[hash1]=hn;
	}else{
	    n=pn=rc->buckets[hash1];
		while(n!=NULL){
		    hv2=n->hash1&0x0000FFFF;
			printf("%s:id=%d hv2=%d\n",__func__,n->id,hv2);
		    if(hv2>hash2){
			    pn=n;
				n=n->left;
			}else if(hv2<hash2){
			    pn=n;
				n=n->right;
			}else{
			    struct recitem *ri=recsearch(rc,n->rp,n->id,NULL);
				int cmpsiz=n->ksiz>ksiz?ksiz:n->ksiz;
			    cmp=reccmpstr(rc,n->rp,ri,key,cmpsiz);
				if(cmp==0) cmp=n->ksiz-ksiz;
				if(cmp>0){
				    pn=n;
					n=n->left;
				}else if(cmp<0){
				    pn=n;
					n=n->right;
				}else{
				    printf("error:same rec\n");
					hashnodefree(rc,hn);
					exit(1);
					return NULL;
				}
			}
		}
		hv2=pn->hash1&0x0000FFFF;
		if(hv2>hash2||(hv2==hash2&&cmp>0)){
		    pn->left=hn;
		}else pn->right=hn;
	}
	if(rc->first==NULL){
		rc->first=hn;
	    hn->pre=hn->next=hn;
	}else{
	    struct hashnode *t=rc->first->pre;
	    rc->first->pre=hn;
		t->next=hn;
		hn->pre=t;
		hn->next=rc->first;
		rc->first=hn;
		/*t=rc->first->pre;
		printf("%s:hn id=%d\n",__func__,t->id);
		t=t->pre;
		while(t!=rc->first->pre){
		    printf("%s:hn id=%d\n",__func__,t->id);
			t=t->pre;
		}*/
	}
	return hn;
}
int hashswap(struct reccache *rc){
    int npg=0,pos;
	struct hashnode *hn=rc->first->pre,*t;
	printf("%s:maxpage=%d npage=%d\n",__func__,rc->maxpage,rc->npage);
	while(hn!=rc->first&&npg<(rc->npage>>1)){
	    if(hn->flag&HN_PIN){
		    printf("%s:id=%d pinned\n",__func__,hn->id);
		    hn=hn->pre;
			continue;
		}
		t=hn->pre;
	    pos=hashnoderemove(rc,hn);
		printf("%s:id=%d pos=%d\n",__func__,hn->id,pos);
		npg+=recfree(rc,hn->rp,pos);
		printf("%s:free %d pg\n",__func__,npg);
		hashnodefree(rc,hn);
		hn=t;
		rc->nrec--;
	}
	printf("%s:swap %d pg\n",__func__,npg);
	return npg;
}
struct recitem *recsearch(struct reccache *rc,struct recpage* rp,int id,int *num){
    int left,right,mid,nrec;
	struct recitem *ri;
	nrec=(rp->lower-sizeof(struct recpage))/sizeof(int16);
	left=0;
	right=nrec-1;
	printf("%s:id=%d nrec=%d\n",__func__,id,nrec);
	while(left<=right){
	    mid=(right+left)>>1;
		ri=(struct recitem*)(*((int16*)((char*)rp+sizeof(struct recpage))+mid)+(char*)rp);
		printf("%s:mid=%d id=%d\n",__func__,mid,ri->id);
		if(ri->id<id){
		    left=mid+1;
		}else if(ri->id>id) right=mid-1;
		else{
		    if(num!=NULL) *num=mid;
			printf("%s:find id=%d pos=%d\n",__func__,id,mid);
		    return ri;
		}
	}
	printf("%s:not find rec\n",__func__);
	return NULL;
}
int reccmpstr(struct reccache *rc,struct recpage *rp,struct recitem *ri,char *key,int ksiz){
    int cmpsiz=ksiz>ri->siz?ri->siz:ksiz;
	int cmp,siz=rc->pagesiz-sizeof(struct recpage);
	int upper;
	struct recpage *t;
	char *ptr=key;
	if(cmpsiz>siz){
	    cmp=strncmp((char*)(ri+1),ptr,siz);
		t=rp->next;
		while(cmp==0&&t!=NULL){
		    cmpsiz-=siz;
			ptr+=siz;
			if(t->lower>sizeof(struct recpage)){
			    upper=*((int16*)((char*)t+sizeof(struct recpage)));
				struct recitem *ri=(struct recitem*)((char*)ri+upper);
				upper+=ri->siz;
			}else upper=t->upper;
			cmp=strncmp((char*)t+upper,ptr,rc->pagesiz-rp->upper);
			if(cmp!=0) return cmp;
		}
		return cmp;
	}
	cmp=strncmp((char*)(ri+1),key,cmpsiz);
	return cmp;
}
int reccmp(struct reccache *rc,struct recpage *rp1,struct recitem *r1,struct recpage* rp2,struct recitem *r2,int cmpsiz){
	int cmp=0,siz,dif;
	struct recitem *min;
	struct recpage *mp,*t;
	if(r1->siz>r2->siz){
		min=r2;
		mp=rp2;
	}else{
		min=r1;
		mp=rp1;
	}
	if(min->siz<cmpsiz) cmpsiz=min->siz;
	//dif=r1->siz-r2->siz;
	if(cmpsiz>rc->pagesiz-sizeof(struct recpage)){
        siz=rc->pagesiz-sizeof(struct recpage);
		cmp=strncmp((char*)(r1+1),(char*)(r2+1),siz);
		t=mp->next;
		while(cmp==0&&t!=NULL){
		    rp1=rp1->next;
			rp2=rp2->next;
			cmpsiz-=siz;
			if(cmpsiz<=rc->pagesiz-sizeof(struct recpage)){
			    int upper1,upper2;
				if(rp1->lower>sizeof(struct recpage)){
				    upper1=*((int16*)((char*)rp1+sizeof(struct recpage)));
					struct recitem *ri=(struct recitem*)((char*)rp1+upper1);
					upper1+=ri->siz;
				}else upper1=rp1->upper;
				if(rp2->lower>sizeof(struct recpage)){
				    upper2=*((int16*)((char*)rp2+sizeof(struct recpage)));
					struct recitem *ri=(struct recitem*)((char*)rp2+upper2);
					upper2+=ri->siz;
				}else upper2=rp2->upper;
			    cmp=strncmp((char*)rp1+upper1,(char*)rp2+upper2,cmpsiz);
				return cmp;
			}
            cmp=strncmp((char*)rp1+sizeof(struct recpage),(char*)rp2+sizeof(struct recpage),siz);
            t=t->next;			
		}
	}
	cmp=strncmp((char*)(r1+1),(char*)(r2+1),cmpsiz);
	return cmp;
}
int hashnoderemove(struct reccache *rc,struct hashnode *hn){
    uint32 hash1=hn->hash1%rc->nbucket;
	struct hashnode *t=rc->buckets[hash1];
	struct hashnode *pt=t;
	int cmp,pos;
	uint16 hash2=hn->hash1&0x0000FFFF;
	uint16 hv2;
	struct recitem *r1,*r2;
	r1=recsearch(rc,hn->rp,hn->id,&pos);
	while(t!=NULL){
	    hv2=t->hash1&0x0000FFFF;
	    if(hv2>hash2){
		    pt=t;
			t=t->left;
		}else if(hv2<hash2){
		    pt=t;
			t=t->right;
		}else if(hn->id!=t->id){//some problem
			r2=recsearch(rc,t->rp,t->id,NULL);
			int cmpsiz=hn->ksiz>t->ksiz?t->ksiz:hn->ksiz;
			cmp=reccmp(rc,t->rp,r2,hn->rp,r1,cmpsiz);
			if(cmp==0) cmp=t->ksiz-hn->ksiz;
		    if(cmp>0){
			    pt=t;
				t=t->left;
			}else if(cmp<0){
			    pt=t;
				t=t->right;
			}else{
			    printf("%s:bad same key find\n",__func__);
				exit(1);
			}
		}else break;
	}
	if(t==NULL){
	    printf("locate error\n");
		exit(1);
	}
	if(t->left==NULL){
	    if(pt==t) rc->buckets[hash1]=t->right; 
	    else if(pt->left==t) pt->left=t->right;
		else pt->right=t->right;
	}
	else if(t->right==NULL){
	    if(pt==t) rc->buckets[hash1]=t->left;
	    else if(pt->left==t) pt->left=t->left;
	    else pt->right=t->left;
	}
	else{
	    struct hashnode *lnp=t->left;
		struct hashnode *ln=lnp;
		while(ln->right!=NULL){
		    lnp=ln;
			ln=ln->right;
		}
		if(pt==t) rc->buckets[hash1]=ln;
		else if(pt->left==t) pt->left=ln;
		else pt->right=ln;
		if(ln!=lnp){
		    lnp->right=ln->left;
		    ln->left=t->left;
		}
		ln->right=t->right;
	}
	if(hn->pre==hn) rc->first=NULL;
	else{
	    hn->pre->next=hn->next;
		hn->next->pre=hn->pre;
		if(hn==rc->first) rc->first=hn->next;
	}
	return pos;
}
int fulllistremove(struct reccache *rc,struct recpage *rp){
    if(rp==rc->fulllist){
		rc->fulllist=rp->listnext;
	    if(rc->fulllist!=NULL) rc->fulllist->listpre=NULL;
	}else{
		if(rp->listnext!=NULL){
			rp->listnext->listpre=rp->listpre;
		}
		rp->listpre->listnext=rp->listnext;
	}
	return 1;
}
int fulllistadd(struct reccache *rc,struct recpage *rp){
    rp->type=PAGE_FULL;
	if(rc->fulllist==NULL){
	     rc->fulllist=rp;
		 rp->listnext=rp->listpre=NULL;
		 return 1;
	}
	rp->listnext=rc->fulllist;
	rc->fulllist->listpre=rp;
	rc->fulllist=rp;
	return 1;
}
int freelistadd(struct reccache *rc,struct recpage* rp){
    rp->type=PAGE_FREE;
	if(rc->freelist==NULL){
	    rc->freelist=rp;
		rp->listnext=rp->listpre=NULL;
		return 1;
	}
	rp->listnext=rc->freelist;
	rc->freelist->listpre=rp;
	rp->listpre=NULL;
	rc->freelist=rp;
	return 1;
}
int recfree(struct reccache *rc,struct recpage* rp,int pos){
	int npg=0;
	void *ptr;
	int i,siz;
	printf("%s:pos=%d\n",__func__,pos);
	int16 *base=(int16*)((char*)rp+sizeof(struct recpage));
	struct recitem *ri=(struct recitem*)(*(base+pos)+(char*)rp);
	ptr=(char*)ri+ri->siz;
	if(ri->siz<=rc->pagesiz-sizeof(struct recpage)-sizeof(int16)){
	    int nrec=(rp->lower-sizeof(struct recpage))/sizeof(int16);
	    rp->upper+=ri->siz;
		for(i=pos;i<nrec-1;i++){
		    ri=(struct recitem*)(*(base+i+1)+(char*)rp);
			siz=ri->siz;
			ptr-=siz;
			memmove(ptr,ri,siz);
			*(base+i)=(char*)ptr-(char*)rp;
		}
		rp->lower-=sizeof(int16);
		if(rp->type==PAGE_FULL){
		    fulllistremove(rc,rp);
			if(rp->upper-rp->lower==rc->pagesiz-sizeof(struct recpage)){
			    freelistadd(rc,rp);
				npg++;
			}else{
			    halflistadd(rc,rp);
			}
		}else{
		    halflistremove(rc,rp);
			if(rp->upper-rp->lower==rc->pagesiz-sizeof(struct recpage)){
			    freelistadd(rc,rp);
				npg++;
			}else{
			    halflistadd(rc,rp);
			}
		}
		return npg;
	}
	struct recpage* tmp=rp->next;
	fulllistremove(rc,rp);
	freelistadd(rc,rp);
	npg++;
	while(tmp->next!=NULL){
		fulllistremove(rc,tmp);
		freelistadd(rc,tmp);
		tmp=tmp->next;
		npg++;
	}
	int nrec=(tmp->lower-sizeof(struct recpage))/sizeof(int16);
	base=(int16*)((char*)tmp+sizeof(struct recpage));
	tmp->upper=rc->pagesiz;
	printf("%s:last page nrec=%d\n",__func__,nrec);
	for(i=0;i<nrec;i++){
	    ri=(struct recitem*)(*(base+i)+(char*)rp);
		tmp->upper-=ri->siz;
		siz=ri->siz;
		memmove((char*)tmp+tmp->upper,ri,siz);
		*(base+i)=tmp->upper;
	}
	if(tmp->type==PAGE_FULL){
	    fulllistremove(rc,tmp);
		if(tmp->upper==rc->pagesiz){
		    freelistadd(rc,tmp);
			npg++;
		}else{
		    halflistadd(rc,tmp);
		}
	}else{
	    halflistremove(rc,tmp);
		if(tmp->upper==rc->pagesiz){
		    freelistadd(rc,tmp);
		    npg++;
		}else{
		    halflistadd(rc,tmp);
		}
	}
	return npg;
}
/*void itoa(int num,char *key,int siz){
   int i;
   for(i=siz-2;i>=0;i--){
      key[i]=num%10+'0';
	  num/=10;
   }
   key[siz-1]='\0';
}

int main(){
    struct reccache *rc=rcnew(3,3,256);
	char buf[32];
	int siz=sizeof(buf)-1,i;
	for(i=0;i<20;i++){
		itoa(i,buf,siz);
		if(!rcput(rc,buf,siz,buf,siz)){
			printf("%s:error put %d\n",__func__,i);
			exit(1);
		}
		free(buf);
	}
	for(i=0;i<20;i++){
		char val[128];
		int vsiz=sizeof(val);
		itoa(i,buf,siz);
		if(rcget(rc,buf,siz,val,&vsiz)==NULL){
			printf("error get\n");
		}else{
			val[vsiz]='\0';
			printf("get siz=%d buf=%s\n",vsiz,val);
		}
	}
	rcfree(rc);
}*/
